#include <stdlib.h>
#include <limits.h>
#include "sort.h"

void swap(int *a, int *b) // 交换两个数据
{
    int t = *a;
    *a = *b;
    *b = t;
    return;
}

int partition(int a[], int p, int r)
{
    int x = a[r], i = p - 1, j; // 取数组最后一个数据赋值x，以x为中间值，划分数据
    for(j = p; j < r; j++)
        if(a[j] <= x) swap(&a[++i], &a[j]); // 如果碰到比x小的数，将它放到前面
    swap(&a[i+1], &a[r]); // 将x放到正确的位置
    return i + 1;         // 返回x的在数组中的位置
}

void quick_sort(int a[], int start, int end)
{
    int mid;
    if(start < end)
    {
        mid = partition(a, start, end);
        quick_sort(a, start, mid - 1);  // 分开两部分递归进行排序
        quick_sort(a, mid + 1, end);
    }
    return;
}

void insertion_sort(int a[], int start, int end) // 排序范围A[start..end]，闭区间
{
    int i, j, key;
    for(i = start + 1; i <= end; i++)
    {
        key = a[i]; j = i - 1;
        while(j >= start && key < a[j])  // 从a[j - 1]开始到a[start]逐个检查，并将比key大的元素推后
            { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;    // 找到合适位置，将元素插入
    }
}

void merge(int a[], int p, int q, int r) // 对A[p..q]和A[q+1..r]进行排序
{
    int i, j, k;
    int *m, *n;

    m = (int *)malloc(sizeof(int) * (q - p + 2));   // 申请额外的空间用于保存中间数据
    n = (int *)malloc(sizeof(int) * (r - q + 1));

    for(i = 0; i < q - p + 1; i++)  m[i] = a[p + i];  // 将前a[p..q]复制到临时数组
    for(j = 0; j < r - q; j++)  n[j] =  a[q + 1 + j]; // 将前a[q+1..r]复制到临时数组

    m[i] = n[j] = INT_MAX;          // 定义为无穷大的数,INT_MAX在limits.h中定义

    for(i = j = 0, k = p; k <= r; k++)   // 两组已经有序的数据开始排序，合成一组
    {
        if(m[i] > n[j])
           a[k] = n[j++];
        else
            a[k] = m[i++];
    }

    free(m); free(n); // 释放内存
}

void merge_sort(int a[], int start, int end)
{
    int mid;
    if(start < end)
    {
        mid = (start + end) / 2;
        merge_sort(a, start, mid);      // 二分递归调用归并排序
        merge_sort(a, mid + 1, end);
        merge(a, start, mid, end);
    }
}

void selection_sort(int a[], int start, int end)
{
    int i, j, min;
    for(i = start; i < end; i++)
    {
        min = i; // 设置一个默认的最小值
        for(j = i + 1; j <= end; j++)
            if(a[j] < a[min]) min = j; // 找出最小的元素
        if(min != i) swap(&a[i], &a[min]); // 交换元素
    }
}

typedef struct heap_t
{
    int *arr;       // 数组
    int len;        // 数组长度
    int size;       // 堆大小
}Heap;

void max_heapify(Heap *hp, int i) // 堆维护
{
    int l, r, largest;
    if(i < 0) return;
    l = ((i + 1) << 1) - 1;                     // i结点的儿子（左边）
    r = (i + 1) << 1;                           // i结点的儿子（右边）
    if(l < hp->size && hp->arr[l] > hp->arr[i]) // 找出arr[l]和arr[i]两个之间最大的一个
        largest = l;
    else largest = i;
    if(r < hp->size && hp->arr[r] > hp->arr[largest]) largest = r; // 找出arr[l]和arr[largest]两个之间最大的一个
    if(largest != i)
    {
        swap(&(hp->arr[i]), &(hp->arr[largest]));
        max_heapify(hp, largest); // 递归维护
    }
    return;
}

void build_max_heap(Heap *hp) // 建堆
{
    int i;
    // 对a[0..(n/2)-1]建堆，[(n/2)..n]是叶节点
    for(i = ((hp->len - 1) >> 1); i >= 0; i--)
        max_heapify(hp, i);
}

void heapSort(Heap *hp)
{
    int i;
    build_max_heap(hp);
    for(i = hp->len - 1; i > 0; i--)
    {
        swap(&(hp->arr[0]), &(hp->arr[i])); //将最大值arr[0]与末尾元素arr[i]交换
        hp->size--;          // 堆大小减1
        max_heapify(hp, 0);  // 调整堆
    }
}

void heap_sort(int a[], int start, int end)
{
    Heap *hp;
    hp = (Heap *)malloc(sizeof(Heap));  // 申请空间
    hp->len = end - start + 1;          // 待排序数据的个数
    hp->size = hp->len;                 // 堆的大小
    hp->arr = a + start;                // 数组起始地址，从a[start]开始排序
    heapSort(hp);
}

void shell_insert(int a[], int n, int d)
{
    int i, j, t;
    for(i = d; i < n; ++i)
    {
        t = a[i];               // 保存带排序的数据
        for(j = i; j >= d && a[j - d] > t; j -= d)
            a[j] = a[j - d];    // 比t大的数据往后移动
        a[j] = t;               // 将待排序数插入正确的位置
    }
}

void shell_sort(int a[], int start, int end)
{
    int d, n;
    n = end - start + 1;            // 计算需要排序的数据个数
    for(d = n/2; d > 0; d /= 2)     // 增量每次都除以2，最后一次增量为1
        shell_insert(a + start, n, d); // 按照增量d进行插入排序
}

void counting_sort(int a[], int start, int end)
{
    int i, k = 0;
    int *c, *b;
    for(i = start; i <= end; i++) // 求出当前最大的数
        if(k < a[i]) { k = a[i]; }
    k += 1; // 后面分配内存的时候可以保存到c[k]
    c = (int *)calloc(k, sizeof(int)); // 分配空间并初始化为0
    b = (int *)malloc(sizeof(int) * (end - start + 1));
    for(i = start; i <= end; i++) // 计数，此时c[i]保存的实际是等于i的元素的个数
        c[a[i]] += 1;
    for(i = 1; i < k; i++)
        c[i] += c[i-1]; //循环过后，此时c[i]保存的是小于或者等于i的个数的值
    for(i = end; i >= start; i--) // 将数据排序到b数组
    {
        b[c[a[i]]-1] = a[i];
        c[a[i]] = c[a[i]] - 1;
    }
    for(i = start; i <= end; i++)
        a[i] = b[i-start];
}

void bubble_sort(int a[], int start, int end)
{
    int i, j;
    for(i = start; i < end; i++)
        for(j = end; j > i; j--)
            if(a[j] < a[j-1]) swap(&a[j], &a[j-1]);
}

void b_insert_sort(int a[], int start, int end)
{
    int i, j, key, mid, low, high;
    for(i = start + 1; i <= end; i++)
    {
        key = a[i]; low = start; high = i - 1;
        while(low <= high)
        {
            mid = (low + high) / 2;
            if(key < a[mid]) high = mid - 1;
            else low = mid + 1;
        }
        for(j = i - 1; j >= high + 1; j--) { a[j + 1] = a[j]; }
        a[high + 1] = key;
    }
}


